第4题用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为叫ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在A上处理时间长,而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业,而且作业处理是不可中断的,每个作业只能被处理一次。现要找出一个最优调度方案,使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。
算法步骤:
(1) 确定候选解上界为最短的单台处理机处理所有作业的完成时间m,
(2) 用P(x,y,k)=l表示前k个作业可以在A用时不超过x且在B用时不超过y时间内处理完成,则p(x,y,k)=p(x-ak,y,k-l) || p(x,y-bk,k-l) (||表示逻辑或操作)。
(3) 得到最短处理时间为min(max(x,y))。